package cn.com.mdx.sort.practice.selinsortedarr;

import cn.com.mdx.sort.SortUtils;

/**
 * <p> 给定两个已经排好序的数组a[],b[]
 * 长度分别是n1和n2，再给定k，k的范围在
 * 0 <= k < (n1 + n2)。设计一个算法找到
 * 排在两个数组中第k大的值，最坏时间复杂度
 * 在 logn 其中n = n1 + n2
 *
 * @author ：huangy
 * @date ：Created in 2020/9/28 3:45 下午
 */
@SuppressWarnings(value = {"rawtypes"})
public class SelectInTwoSortedArray {

    /**
     * @param sortedArray1 已排序的数组1
     * @param sortedArray2 已排序的数组2
     * @param k            第k大的数
     * @return Comparable
     * @Author huangy
     * @description //TODO 查找两个排序数组中第k大的数 暴力方式 时间复杂度n
     * @date 11:26 上午 2020/9/28
     **/
    public static Comparable force(Comparable[] sortedArray1, Comparable[] sortedArray2, int k) {
        //检测输入数组有效性
        checkArray(sortedArray1);
        checkArray(sortedArray2);

        //第一个数组的长度
        int N1 = sortedArray1.length;
        //第二个数组的长度
        int N2 = sortedArray2.length;
        if (k < 0 || k >= (N1 + N2)) throw new IllegalArgumentException("传入的k值不符合要求");
        //特殊情况处理
        Comparable specialCaseComparable = specialCase(sortedArray1, sortedArray2, k);
        if (specialCaseComparable != null) return specialCaseComparable;
        int i = 0, j = 0;
        Comparable[] tmp = new Integer[N1 + N2];
        //合并两个有序数组
        for (int q = 0; q < tmp.length; q++) {
            if (i > N1 - 1) tmp[q] = sortedArray2[j++];
            else if (j > N2 - 1) tmp[q] = sortedArray1[i++];
            else if (SortUtils.less(sortedArray1[i], sortedArray2[j])) tmp[q] = sortedArray1[i++];
            else tmp[q] = sortedArray2[j++];
        }
        return tmp[k];
    }

    /**
     * @param array 要检测的数组
     * @return void
     * @Author huangy
     * @description //TODO 检测数组是否合法
     * @date 10:59 上午 2020/10/10
     **/
    private static void checkArray(Comparable[] array) {
        if (array == null || array.length <= 0) throw new IllegalArgumentException("数组为空无法进行查找");
    }

    /**
     * @param sortedArray1 已排序数组1
     * @param sortedArray2 已排序数组2
     * @param k            排序第k的元素
     * @return java.lang.Comparable
     * @Author huangy
     * @description //TODO 有序数组查找特殊情况处理：临界值 线性有序
     * @date 9:40 上午 2020/10/9
     **/
    private static Comparable specialCase(Comparable[] sortedArray1, Comparable[] sortedArray2, int k) {
        int N1 = sortedArray1.length;
        int N2 = sortedArray2.length;
        //临界值判断
        //当k为0的情况
        if (k == 0)
            if (SortUtils.less(sortedArray1[0], sortedArray2[0]) ||
                    SortUtils.equals(sortedArray1[0], sortedArray2[0]))
                return sortedArray1[0];
            else return sortedArray2[0];
        //当k为两数组末位置的情况
        if (k == (N1 + N2 - 1))
            if (SortUtils.less(sortedArray1[N1 - 1], sortedArray2[N2 - 1])) return sortedArray2[N2 - 1];
            else return sortedArray1[N1 - 1];
        //如果array1和array2是线性有序的，即array1的最大值小于array2的最小值
        //或者array2的最大值小于array1最小值
        if (SortUtils.less(sortedArray1[N1 - 1], sortedArray2[0]) ||
                SortUtils.equals(sortedArray1[N1 - 1], sortedArray2[0])) {
            if (k < N1) return sortedArray1[k];
            else return sortedArray2[k - N1];
        } else if (SortUtils.less(sortedArray2[N2 - 1], sortedArray1[0]) ||
                SortUtils.equals(sortedArray2[N2 - 1], sortedArray1[0])) {
            if (k < N2) return sortedArray2[k];
            else return sortedArray1[k - N2];
        }
        //当有一个数组长度小于要寻找的长度的1/2时
//        if (N1 <= k / 2 && SortUtils.less(sortedArray1[N1 - 1], sortedArray2[k - N1]))
//            return sortedArray2[k - N1];
//        if (N2 <= k / 2 && SortUtils.less(sortedArray2[N2 - 1], sortedArray2[k - N2]))
//            return sortedArray2[k - N2];
        return null;
    }

    /**
     * <p> 思路
     * 找到两个
     *
     * @param sortedArray1 已排序的数组1
     * @param sortedArray2 已排序的数组2
     * @param k            第k大的数
     * @return void
     * @Author huangy
     * @description //TODO 查找两个排序数组中第k大的数 快速方式 时间复杂度logn
     * @date 11:26 上午 2020/9/28
     **/
    public static Comparable quick(Comparable[] sortedArray1, Comparable[] sortedArray2, int k) {
        //检测数组有效性
        checkArray(sortedArray1);
        checkArray(sortedArray2);
        int N1 = sortedArray1.length;
        int N2 = sortedArray2.length;
        if (k < 0 || k >= (N1 + N2)) throw new IllegalArgumentException("传入的k值不符合要求");
        //特殊情况处理
        Comparable specialCaseComparable = specialCase(sortedArray1, sortedArray2, k);
        if (specialCaseComparable != null) return specialCaseComparable;
        int arrayIndex1 = (k + 1) / 2 - 1;
        int arrayIndex2 = (k + 1) - (k + 1) / 2 - 1;
        //一个数组的长度小于要寻找k值的一半
        if (N1 <= k / 2) {
            arrayIndex1 = N1 - 1;
            arrayIndex2 = k - arrayIndex1 - 1;
        } else if (N2 <= k / 2) {
            arrayIndex2 = N2 - 1;
            arrayIndex1 = k - arrayIndex2 - 1;
        }
        return find(sortedArray1, sortedArray2, arrayIndex1, arrayIndex2, k);
    }

    /**
     * <p> 思路
     * 将k 分为
     *
     * @param sortedArray1 已排序的数组1
     * @param sortedArray2 已排序的数组2
     * @param arrayIndex1  第一个数组的索引
     * @param arrayIndex2  第二个数组的索引
     * @param k            第k大的数
     * @return void
     * @Author huangy
     * @description //TODO 比较数组中
     * @date 11:26 上午 2020/9/28
     **/
    private static Comparable find(Comparable[] sortedArray1, Comparable[] sortedArray2,
                                   int arrayIndex1, int arrayIndex2, int k) {
        //如果有索引为负值，直接返回另一个数组中对应的值
        if (arrayIndex1 < 0) return sortedArray2[arrayIndex2];
        if (arrayIndex2 < 0) return sortedArray1[arrayIndex1];
        //两个数组索引都在数组末尾
        if (arrayIndex1 == sortedArray1.length - 1 && arrayIndex2 == sortedArray2.length - 1)
            if (SortUtils.great(sortedArray1[arrayIndex1], sortedArray2[arrayIndex2]))
                return sortedArray1[arrayIndex1];
            else return sortedArray2[arrayIndex2];
        //第一个索引在数组末尾
        if (arrayIndex1 == sortedArray1.length - 1)
            if (SortUtils.great(sortedArray2[arrayIndex2], sortedArray1[arrayIndex1]))
                return sortedArray2[arrayIndex2];
            else if (SortUtils.less(sortedArray1[arrayIndex1], sortedArray2[arrayIndex2 + 1])
                    || SortUtils.equals(sortedArray1[arrayIndex1], sortedArray2[arrayIndex2 + 1]))
                return sortedArray1[arrayIndex1];
            else return find(sortedArray1, sortedArray2, arrayIndex1 - 1, arrayIndex2 + 1, k);
        //第二个索引在数组末尾
        if (arrayIndex2 == sortedArray2.length - 1)
            if (SortUtils.great(sortedArray1[arrayIndex1], sortedArray2[arrayIndex2]))
                return sortedArray1[arrayIndex1];
            else if (SortUtils.less(sortedArray2[arrayIndex2], sortedArray1[arrayIndex1 + 1])
                    || SortUtils.equals(sortedArray2[arrayIndex2], sortedArray1[arrayIndex1 + 1]))
                return sortedArray2[arrayIndex2];
            else return find(sortedArray1, sortedArray2, arrayIndex1 + 1, arrayIndex2 - 1, k);
        //都不在数组末尾的情况
        if (SortUtils.great(sortedArray1[arrayIndex1], sortedArray2[arrayIndex2]))
            if (SortUtils.less(sortedArray1[arrayIndex1], sortedArray2[arrayIndex2 + 1])
                    || SortUtils.equals(sortedArray1[arrayIndex1], sortedArray2[arrayIndex2 + 1]))
                return sortedArray1[arrayIndex1];
            else return find(sortedArray1, sortedArray2, arrayIndex1 - 1, arrayIndex2 + 1, k);
        if (SortUtils.great(sortedArray2[arrayIndex2], sortedArray1[arrayIndex1]))
            if (SortUtils.less(sortedArray2[arrayIndex2], sortedArray1[arrayIndex1 + 1])
                    || SortUtils.equals(sortedArray2[arrayIndex2], sortedArray1[arrayIndex1 + 1]))
                return sortedArray2[arrayIndex2];
            else return find(sortedArray1, sortedArray2, arrayIndex1 + 1, arrayIndex2 - 1, k);
        return sortedArray1[arrayIndex1];
    }

    public static void main(String[] args) {
        Integer[] sortedArray1 = {1, 3, 7, 10, 11, 24, 28, 35, 39, 55, 89, 176, 203, 205, 333, 1004, 2045, 3024};
        Integer[] sortedArray2 = {5, 8, 13, 19, 21, 22, 23, 29, 37, 45, 54, 55, 102, 167, 205, 2310, 2390};
//        int k = 1;
//        int value1 = (int) quick(sortedArray1, sortedArray2, k);
//        System.out.println("两个数组第" + k + "小的元素是：" + value1);
        for (int i = 0; i < sortedArray1.length + sortedArray2.length; i++) {
            int value = (int) quick(sortedArray1, sortedArray2, i);
            System.out.println("两个数组第" + i + "小的元素是：" + value);
        }
    }

}
